Comparing the Algorithm Techniques for Minimum Spanning Tree
The number of edges in a connected graph is
$$ n - 1 \leq m \leq \frac{n(n - 1)}{2}$$
한 그래프에서 정점의 개수를 n이라고 할 때, 이음선 개수(m)의 범위는 n - 1개에서 부터 n(n - 1)/2 (1부터 n-1까지의 합)이다.
Time Complexity Analysis
| Problem | Algoritm Technique | Time Complexity (시간복잡도) |
Sparse Graph (희소 그래프) |
Dense Graph (밀집 그래프) |
|---|---|---|---|---|
| MST | Prim’s Algorithm | $\Theta(n^2)$ | $\Theta(n^2)$ | $\Theta(n^2)$ |
| MST | Kruskal’s Algorithm | $\Theta(mlogm) \ \text{and} \ \Theta(n^2lgn)$ | $\Theta(mlgm)$ | $\Theta(n^2lgn)$ |
For a graph whose number of edges m is near the low end of these limits (the graph is very sparse), Kruskal’s algorithm is $\Theta(nlgn)$, which means that Kruskal's algorithm should be faster. However, for a graph whose number of edges is near the high end (the graph is highly connected), Kruskal’s algorithm is $\Theta(n^2lgn)$, which means that Prim's algorithm should be faster.
이음선의 개수가 하한선 근처(n - 1에 근접)인 경우 희소 그래프(sparse graph)이고, 상한선 근처(n(n - 1)/2에 근접)인 경우는 밀집 그래프(dense graph) 이다. 결론적으로 희소 그래프의 경우 Kruskal 알고리즘의 성능이, 밀집 그래프의 경우엔 Prim 알고리즘의 성능이 효율적임을 알 수 있다.